'''
难度：中等
类型：数组
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
'''
class Solution:
    def threeSum(self, nums):
        # nums.sort()
        # [-4,-1,0,1,2,3,4]
        result=[]
        n = len(nums)
        nums.sort()
        for i in range(n-2):
            if  nums[i] + nums[i+1] + nums[i+2] >0:
                break
            if nums[i] + nums[n-1] + nums[n-2] < 0:
                continue
            l , r = i+1,n-1
            while l < r:
                temp = nums[i]+nums[l]+nums[r]
                if temp ==0:
                    result.append([nums[i],nums[l],nums[r]])
                    while l+1 <r and nums[l]==nums[l+1]:
                        l =l+1
                    l =l+1
                    while l< r-1 and nums[r]==nums[r-1]:
                        r=r-1
                    r=r-1
                elif temp<0:
                    l=l+1
                else:
                    r=r-1
        return result
# 方法二

    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res = []
        for i in range(len(nums)-2):
            # 因为是排序好的数组，如果最小的都大于0可以直接排除
            if nums[i] > 0: break
            # 排除i的重复值
            if i > 0 and nums[i] == nums[i-1]: continue
            l,r = i+1, len(nums)-1
            while l < r:
                sum = nums[i] + nums[l] + nums[r]
                if sum == 0:
                    res.append([nums[i],nums[l],nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
                elif sum < 0:
                    l += 1
                else:
                    r -= 1
        return res
 
        



if __name__=="__main__":
    solo = Solution()
    result = solo.threeSum([-1,0,1,2,-1,-4])
    print(result)